4.18

题目

Let $C$ be a language. Prove that $C$ is Turing-recognizable iff a decidable language $D$ exists such that

C = {x ∣ \exists y (⟨ x, y ⟩ \in D)} .

点击展开

从 decidable 推 recognizable 是显然的，只需要将 y 按标准字符串序依次测试。

从 recognizable 推 decidable 需要构造 D，将 C 拆解为存在性问题
直接在自然语言基础上变换：x 被 C 识别，等价于 x 经过某图灵机计算得到接受状态，等价于存在计算使得 x 经其得到接受状态。每个计算都有步数，枚举步数即可。

点击展开

从 recognizable 推 decidable：记 C 对应的图灵机是 TC，构造图灵机 TD，对输入 $⟨ x, y ⟩$ ，在 x 上模拟 TC 的计算 $| y |$ 步，如果 TC 接受则 TD 接受，否则拒绝。

另一个暴力的方法是直接让 y 编码计算过程，即 configuration 的序列。